<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Complete Tree Search with Heuristics
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial087.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial086.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial089.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc164">12.2</A>&nbsp;&nbsp;Complete Tree Search with Heuristics</H2><UL>
<LI><A HREF="tutorial088.html#toc78">Search Trees</A>
<LI><A HREF="tutorial088.html#toc79">Variable Selection</A>
<LI><A HREF="tutorial088.html#toc80">Value Selection</A>
<LI><A HREF="tutorial088.html#toc81">Example</A>
<LI><A HREF="tutorial088.html#toc82">Counting Backtracks</A>
</UL>


<A NAME="@default311"></A>
There is one form of tree search which is especially economic: 
depth-first, left-to-right search by backtracking. It allows
a search tree to be traversed systematically while requiring only a stack
of maximum depth N for bookkeeping. Most other strategies of tree
search (e.g. breadth-first) have exponential memory requirements. 
This unique property is the reason why backtracking is a built feature
of ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>. Note that the main disadvantage of the depth-first
strategy (the danger of going down an infinite branch) does not come
into play here because we deal with finite search trees.<BR>
<BR>
<A NAME="@default312"></A>
Sometimes depth-first search and heuristic search are treated as antonyms.
This is only justified when the shape of the search tree is statically fixed.
Our case is different: we have the freedom of deciding on the shape of every
sub-tree before we start to traverse it depth-first. While this does not
allow for absolutely <EM>any</EM> order of visiting the leaves of the search tree,
it does provide considerable flexibility. This flexibility can be exploited
by variable and value selection strategies.<BR>
<BR>
<A NAME="toc78"></A>
<H3 CLASS="subsection"><A NAME="htoc165">12.2.1</A>&nbsp;&nbsp;Search Trees</H3>

In general, the nodes of a search tree represent <EM>choices</EM>.
<A NAME="@default313"></A>
These choices should be mutually exclusive and therefore partition the
<A NAME="@default314"></A>
search space into two or more disjoint sub-spaces.
In other words, the original problem is reduced to a disjunction
of simpler sub-problems.<BR>
<BR>
In the case of finite-domain problems, the most common form of choice
is to choose a particular value for a problem variable
(this technique is often called
<A NAME="@default315"></A>
<EM>labeling</EM>).
For a boolean variable, this means setting the variable to 0 in one
branch of the search tree and to 1 in the other.
In ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>, this can be written as a disjunction
(which is implemented by backtracking):
<BLOCKQUOTE CLASS="quote"><PRE>
( X1=0 ; X1=1 )
</PRE></BLOCKQUOTE>
Other forms of choices are possible. If X2 is a variable that can take
integer values from 0 to 3 (assume it has been declared as <CODE>X2::0..3</CODE>),
we can make a n-ary search tree node by writing
<BLOCKQUOTE CLASS="quote"><PRE>
( X2=0 ; X2=1 ; X2=2 ; X2=3 )
</PRE></BLOCKQUOTE>
or more compactly
<BLOCKQUOTE CLASS="quote"><PRE>
indomain(X2)
</PRE></BLOCKQUOTE>
However, choices do not necessarily involve choosing a concrete value
for a variable. It is also possible to make disjoint choices by
<A NAME="@default316"></A>
<EM>domain splitting</EM>, e.g.
<BLOCKQUOTE CLASS="quote"><PRE>
( X2 #=&lt; 1 ; X2 #&gt;= 2 )
</PRE></BLOCKQUOTE>
or by choosing a value in one branch and excluding it in the other:
<BLOCKQUOTE CLASS="quote"><PRE>
( X2 = 0 ; X2 #&gt;= 1 )
</PRE></BLOCKQUOTE>
In the following examples, we will mainly use simple labeling,
which means that the search tree nodes correspond to a variable
and a node's branches correspond to the different values that the
variable can take.<BR>
<BR>
<A NAME="toc79"></A>
<H3 CLASS="subsection"><A NAME="htoc166">12.2.2</A>&nbsp;&nbsp;Variable Selection</H3>
<A NAME="@default317"></A>

<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<IMG SRC="tutorial036.gif">
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 12.5: The effect of variable selection</DIV><BR>
<BR>

<A NAME="figvarsel"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
Figure <A HREF="#figvarsel">12.5</A> shows how variable selection reshapes a search tree.
If we decide to choose values for X1 first (at the root of the search tree)
and values for X2 second, then the search tree has one particular shape.
If we now assume a depth-first, left-to-right traversal by backtracking,
this corresponds to one particular order of visiting the leaves of the tree:
(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3).<BR>
<BR>
If we decide to choose values for X2 first and X1 second, then the tree and
consequently the order of visiting the leaves is different:
(0,0), (1,0), (0,1), (1,1), (0,2), (1,2), (0,3), (1,3).<BR>
<BR>
While with 2 variables there are only 2 variable selection strategies,
this number grows exponentially with the number of variables. For 5
variables there are already 2<SUP>2<SUP>5</SUP>&minus;1</SUP> = 2147483648 different variable selection
strategies to choose from.<BR>
<BR>
Note that the example shows something else: If the domains of the variables
are different, then the variable selection can change the number of internal
nodes in the tree (but not the number of leaves). To keep the number of nodes
down, variables with small domains should be selected first.<BR>
<BR>
<A NAME="toc80"></A>
<H3 CLASS="subsection"><A NAME="htoc167">12.2.3</A>&nbsp;&nbsp;Value Selection</H3>
<A NAME="@default318"></A>

The other way to change the search tree is value selection, i.e. reordering
the child nodes of a node by choosing the 
values from the domain of a variable in a particular order.
Figure <A HREF="#figvalsel">12.6</A> shows how this can change the order of visiting the
leaves:
(1,2), (1,1), (1,0), (1,3), (0,1), (0,3), (0,0), (0,2).
<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<IMG SRC="tutorial037.gif">
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 12.6: The effect of value selection</DIV><BR>
<BR>

<A NAME="figvalsel"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
By combining variable and value selection alone, a large number of different
heuristics can be implemented.
To give an idea of the numbers involved, table <A HREF="#visits">12.7</A> shows the search
space sizes, the number of possible search space traversal orderings,
and the number of orderings
that can be obtained by variable and value selection (assuming domain size 2).
<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<TABLE BORDER=1 CELLSPACING=0 CELLPADDING=1>
<TR><TD ALIGN=left NOWRAP>Variables</TD>
<TD ALIGN=left NOWRAP>Search space</TD>
<TD ALIGN=left NOWRAP>Visiting orders</TD>
<TD ALIGN=left NOWRAP>Selection Strategies</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>1</TD>
<TD ALIGN=left NOWRAP>2</TD>
<TD ALIGN=left NOWRAP>2</TD>
<TD ALIGN=left NOWRAP>2</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>2</TD>
<TD ALIGN=left NOWRAP>4</TD>
<TD ALIGN=left NOWRAP>24</TD>
<TD ALIGN=left NOWRAP>16</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>3</TD>
<TD ALIGN=left NOWRAP>8</TD>
<TD ALIGN=left NOWRAP>40320</TD>
<TD ALIGN=left NOWRAP>336</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>4</TD>
<TD ALIGN=left NOWRAP>16</TD>
<TD ALIGN=left NOWRAP>2.1*10<SUP>13</SUP></TD>
<TD ALIGN=left NOWRAP>1.8*10<SUP>7</SUP></TD>
</TR>
<TR><TD ALIGN=left NOWRAP>5</TD>
<TD ALIGN=left NOWRAP>32</TD>
<TD ALIGN=left NOWRAP>2.6*10<SUP>35</SUP></TD>
<TD ALIGN=left NOWRAP>3.5*10<SUP>15</SUP></TD>
</TR>
<TR><TD ALIGN=left NOWRAP>n</TD>
<TD ALIGN=left NOWRAP>2<SUP><I>n</I></SUP></TD>
<TD ALIGN=left NOWRAP>2<SUP><I>n</I></SUP>!</TD>
<TD ALIGN=left NOWRAP>2<SUP>2<SUP><I>n</I></SUP>&minus;1</SUP> &Pi;<SUB><I>i</I>=0</SUB><SUP><I>n</I>&minus;1</SUP> (<I>n</I>&minus;1)<SUP>2<SUP><I>i</I></SUP></SUP></TD>
</TR></TABLE>
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 12.7: Flexibility of Variable/Value Selection Strategies</DIV><BR>
<BR>

<A NAME="visits"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<A NAME="toc81"></A>
<H3 CLASS="subsection"><A NAME="htoc168">12.2.4</A>&nbsp;&nbsp;Example</H3>

<A NAME="@default319"></A>
We use the famous N-Queens problem to illustrate how heuristics can be applied
to backtrack search through variable and value selection.
We model the problem with one variable per queen, assuming that each queen
occupies one colunm. The variables range from 1 to N and indicate the row
in which the queen is being placed. The constraints ensure that no two
queens occupy the same row or diagonal:
<A NAME="queenscode"></A>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(ic).

queens(N, Board) :-
        length(Board, N),
        Board :: 1..N,
        ( fromto(Board, [Q1|Cols], Cols, []) do
            ( foreach(Q2, Cols), count(Dist,1,_), param(Q1) do
                noattack(Q1, Q2, Dist)
            )
        ).

    noattack(Q1,Q2,Dist) :-
        Q2 #<CODE>\</CODE>= Q1,
        Q2 - Q1 #<CODE>\</CODE>= Dist,
        Q1 - Q2 #<CODE>\</CODE>= Dist.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
We are looking for a first solution to the 16-queens problem by calling
<BLOCKQUOTE CLASS="quote"><PRE>
?- queens(16, Vars),   % model
   labeling(Vars).     % search
</PRE></BLOCKQUOTE>
We start naively, using the pre-defined labeling-predicate that comes with the
<EM>ic</EM> library. It is defined as follows:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
labeling(AllVars) :-
        ( foreach(Var, AllVars) do
            indomain(Var)                       % select value
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
The strategy here is simply to select the variables
from left to right as they occur in the list, and they are
assigned values starting from the lowest to the numerically highest they can
take (this is the definition of indomain/1).
A solution is found after 542 backtracks
(see section <A HREF="#countbt">12.2.5</A> below for how to count backtracks).<BR>
<BR>
A first improvement is to employ a
<B>general-purpose variable-selection heuristic</B>,
<A NAME="@default320"></A>
the so called first-fail principle. It requires to label the
variables with the smallest domain first. This reduces the branching
factor at the root of the search tree and the total number of internal nodes.
<A NAME="@default321"></A>
The delete/5 predicate from the <EM>ic_search</EM> library
implements this strategy for finite integer domains.
Using delete/5, we can redefine our labeling-routine as follows:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(ic_search).
labeling_b(AllVars) :-
        ( fromto(AllVars, Vars, VarsRem, []) do
            delete(Var, Vars, VarsRem, 0, first_fail), % dynamic var-select
            indomain(Var)                              % select value
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
Indeed, for the 16-queens example, this leads to a dramatic improvement,
the first solution is found with only 3 backtracks now.
But caution is necessary: The 256-queens instance for example solves
nicely with the naive strategy, but our improvement leads to a
disappointment: the time increases dramatically!
This is not uncommmon with heuristics: one has to keep in mind that the
search space is not reduced, just re-shaped. Heuristics that yield good
results with some problems can be useless or counter-productive with others.
Even different instances of the same problem can exhibit widely different
characteristics.<BR>
<BR>
Let us try to employ a <B>problem-specific heuristic</B>:
<A NAME="@default322"></A>
Chess players know that pieces in the middle of the board are more
useful because they can attack more fields. We could therefore start
placing queens in the middle of the board to reduce the number of
unattacked fields earlier. We can achieve that simply by pre-ordering the
variables such that the middle ones are first in the list:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
labeling_c(AllVars) :-
        middle_first(AllVars, AllVarsPreOrdered), % static var-select
        ( foreach(Var, AllVarsPreOrdered) do
            indomain(Var)                         % select value
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
The implementation of middle_first/2 requries a bit of list manipulation
<A NAME="@default323"></A>
and uses primitives from the lists-library:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(lists).

middle_first(List, Ordered) :-
        halve(List, Front, Back),
        reverse(Front, RevFront),
        splice(Back, RevFront, Ordered).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
This strategy also improves things for the 16-queens instance, the
first solution requires 17 backtracks.<BR>
<BR>
We can now improve things further by <B>combining</B> the two
variable-selection strategies:
When we pre-order the variables such that the middle ones are first,
<A NAME="@default324"></A>
the delete/5 predicate will prefer middle variables when several
have the same domain size:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
labeling_d(AllVars) :-
        middle_first(AllVars, AllVarsPreOrdered), % static var-select
        ( fromto(AllVarsPreOrdered, Vars, VarsRem, []) do
            delete(Var, Vars, VarsRem, 0, first_fail),  % dynamic var-select
            indomain(Var)                       % select value
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
The result is positive: for the 16-queens instance,
the number of backtracks goes down to zero,
and more difficult instances become solvable!<BR>
<BR>
Actually, we have not yet implemented our intuitive heuristics properly.
We start placing queens in the middle columns, but not on the middle rows.
With our model, that can only be achieved by <B>changing the value selection</B>,
ie. setting the variables to values in the middle of their domain first.
For this we can use indomain/2, a more flexible variant of indomain/1,
provided by the <EM>ic_search</EM> library.
It allows us to specify that we want to start labeling with the middle value
in the domain:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
labeling_e(AllVars) :-
        middle_first(AllVars, AllVarsPreOrdered), % static var-select
        ( fromto(AllVarsPreOrdered, Vars, VarsRem, []) do
            delete(Var, Vars, VarsRem, 0, first_fail),  % dynamic var-select
            indomain(Var, middle)                 % select value
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
Surprisingly, this improvement again increases the backtrack count for
16-queens again to 3.
However, when looking at a number of different instances of the problem,
we can observe that the overall behaviour has improved and the
performance has become more predictable than with the
initial more naive strategies.
Figure <A HREF="#queensresult">12.2.4</A> shows the behaviour of the different
strategies on various problem sizes.
<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<TABLE BORDER=1 CELLSPACING=0 CELLPADDING=1>
<TR><TD ALIGN=left NOWRAP>N =</TD>
<TD ALIGN=left NOWRAP>8</TD>
<TD ALIGN=left NOWRAP>12</TD>
<TD ALIGN=left NOWRAP>14</TD>
<TD ALIGN=left NOWRAP>16</TD>
<TD ALIGN=left NOWRAP>32</TD>
<TD ALIGN=left NOWRAP>64</TD>
<TD ALIGN=left NOWRAP>128</TD>
<TD ALIGN=left NOWRAP>256</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>labeling_a</TD>
<TD ALIGN=left NOWRAP>10</TD>
<TD ALIGN=left NOWRAP>15</TD>
<TD ALIGN=left NOWRAP>103</TD>
<TD ALIGN=left NOWRAP>542</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>labeling_b</TD>
<TD ALIGN=left NOWRAP>10</TD>
<TD ALIGN=left NOWRAP>16</TD>
<TD ALIGN=left NOWRAP>11</TD>
<TD ALIGN=left NOWRAP>3</TD>
<TD ALIGN=left NOWRAP>4</TD>
<TD ALIGN=left NOWRAP>148</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>labeling_c</TD>
<TD ALIGN=left NOWRAP>0</TD>
<TD ALIGN=left NOWRAP>3</TD>
<TD ALIGN=left NOWRAP>22</TD>
<TD ALIGN=left NOWRAP>17</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>labeling_d</TD>
<TD ALIGN=left NOWRAP>0</TD>
<TD ALIGN=left NOWRAP>0</TD>
<TD ALIGN=left NOWRAP>1</TD>
<TD ALIGN=left NOWRAP>0</TD>
<TD ALIGN=left NOWRAP>1</TD>
<TD ALIGN=left NOWRAP>1</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>labeling_e</TD>
<TD ALIGN=left NOWRAP>3</TD>
<TD ALIGN=left NOWRAP>3</TD>
<TD ALIGN=left NOWRAP>38</TD>
<TD ALIGN=left NOWRAP>3</TD>
<TD ALIGN=left NOWRAP>7</TD>
<TD ALIGN=left NOWRAP>1</TD>
<TD ALIGN=left NOWRAP>0</TD>
<TD ALIGN=left NOWRAP>0</TD>
</TR></TABLE>
</DIV>
<A NAME="queensresult"></A>
<BR>
<BR>
<DIV CLASS="center">Figure 12.8: N-Queens with different labeling strategies: Number of backtracks</DIV><BR>
<BR>

<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<A NAME="toc82"></A>
<H3 CLASS="subsection"><A NAME="htoc169">12.2.5</A>&nbsp;&nbsp;Counting Backtracks</H3>
<A NAME="@default325"></A>

<A NAME="countbt"></A>
An interesting piece of information during program development is the
number of backtracks. It is a good measure for the quality of
both constraint propagation and search heuristics.
We can instrument our labeling routine as follows:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
labeling(AllVars) :-
        init_backtracks,
        ( foreach(Var, AllVars) do
            count_backtracks,       % insert this before choice!
            indomain(Var)
        ),
        get_backtracks(B),
        printf("Solution found after %d backtracks%n", [B]).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
The backtrack counter itself can be implemented by the code below.
It uses a non-logical counter variable (backtracks) and an additional
flag (deep_fail) which ensures that backtracking to exhausted choices
does not increment the count.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- local variable(backtracks), variable(deep_fail).

init_backtracks :-
        setval(backtracks,0).

get_backtracks(B) :-
        getval(backtracks,B).

count_backtracks :-
        setval(deep_fail,false).
count_backtracks :-
        getval(deep_fail,false),        % may fail
        setval(deep_fail,true),
        incval(backtracks),
        fail.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
Note that there are other possible ways of defining the number of backtracks.
However, the one suggested here has the following useful properties:
<UL CLASS="itemize"><LI CLASS="li-itemize">
Shallow backtracking (an attempt to instantiate a variable which
 <A NAME="@default326"></A>
 causes immediate failure due to constraint propagation) is not counted.
 If constraint propagation works well, the count is therefore zero.
<LI CLASS="li-itemize">With a perfect heuristic, the first solution is found with zero
 backtracks.
<LI CLASS="li-itemize">If there are N solutions, the best achievable value is N (one backtrack
 per solution). Higher values indicate an opportunity to improve pruning
 by constraints.
</UL>
The search/6 predicates from the libary <TT>ic_search</TT> 
have this backtrack counter built-in.<BR>
<BR>
<HR>
<A HREF="tutorial087.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial086.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial089.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
